package com.xyhuo.leetcode.january;

/**
 * 字符串中的额外字符
 * https://leetcode.cn/problems/extra-characters-in-a-string/
 *
 * @time 2024/1/9
 */
public class MinExtraChar {

//    public static void main(String[] args) {
//        MinExtraChar mec = new MinExtraChar();
//        String[] dictionary = {"xo", "e"};
//        mec.minExtraChar("zaizdhxoimmraiakbak", dictionary);
//    }

    public int minExtraChar(String s, String[] dictionary) {

        int length = s.length();
        int[] dp = new int[length];
        for (int i = 0; i < length; i++) {
            int extra = Integer.MAX_VALUE;
            boolean find = false;
            for (String item : dictionary) {
                int itemLen = item.length();
                if (i - itemLen + 1 >= 0) {
                    String tmpStr = s.substring(i - itemLen + 1, i + 1);
                    if (tmpStr.equals(item)) {
                        find = true;
                        int tmpExtra = i - itemLen < 0 ? 0 : dp[i - itemLen];
                        if (tmpExtra < extra) {
                            extra = tmpExtra;
                        }
                    }
                }
            }
            if (!find) {
                dp[i] = (i - 1 >= 0 ? dp[i - 1] : 0) + 1;
            } else {
                if (i - 1 >= 0 && dp[i - 1] + 1 < extra) {
                    dp[i] = dp[i - 1] + 1;
                } else {
                    dp[i] = extra;
                }
            }
        }
        return dp[length - 1];
    }
}
